1. Field of the Invention
Apparatuses and methods consistent with the present invention relate to processing entries such as packets and the like in communication systems, and more particularly to a packet classification method using field level tries in classifying packets in routers and a packet classification apparatus implementing the method.
2. Description of the Related Art
In processing packets in communication systems such as the Internet, each transit node in the packet-forwarding path interprets a destination address and then decides to which output node or link a packet is forwarded. In various communication systems, diverse types of services are provided based on a destination address, origination address, or other data in a header of each packet. The different types of services include, for example, priorities in treating or forwarding packets, fares to be paid for the transmissions, packet-processing rejections to specific senders, etc.
Since current systems may process enormous amounts of packets (in general, data entries), the systems find out the content from the received packets and decide in which forms packets are processed, accordingly, in a very short time and at a high speed.
In order to provide users with more advanced services such as service level agreements, virtual private networking (VPN), QoS, and so on, over future IP networks, IP packets incoming from routers and the like are to be classified based on a desired standard, which is referred to as “packet classification”. This packet classification is performed based on multi-field lookup in the long run since values of various packet fields are looked up.
In other words, the packet classification is performed through processing packets with reference to various fields, such as a source address field, a destination address field, a protocol ID field, a port number field, and so on, in one packet, differently from existing IP destination address lookup. Therefore, more time and memory are basically required, and a method solving such a problem has not been fully studied.
FIG. 1 to FIG. 3 are views for illustrating conventional packet classification methods.
Table 1 shows a packet classifier for configuring conventional methods.
TABLE 1FilterF1F2R100*11*R200*1*R310*1*R40*01*R50*10*R60*1*R7*00*
Typical methods for conventional packet classification include the grid-of-tries as shown in FIG. 1, a geometric method represented by the range lookup of FIG. 2, a heuristic method represented by a recursive flow classification of FIG. 3, and so on.
Of these methods, a data structure based on the grid-of-tries combines advantages of the standard hierarchical trie and the set-pruning trie, and has the query time complexity of O (dW) and the storage complexity of O (NdW), based on the number of header fields d (i.e., dimension) of W bit length on which N classification rules apply. These characteristics are obtained to introduce a switch pointer into a data structure. However, the formation of the switch pointer in bit level ensures the storage complexity of O (NdW), and a query procedure must be implemented bit by bit. Real applications asking for implementations do not accept the bit-by-bit query procedure (or classification).
In classifying packets, important considerations include classification rates, memory size, the number of classification rules, the number of reference fields, rule update time, and worst-case performances.
That is, in order for the packet classification to secure maximum performances using an available memory, it is important to solve the problems relating to achieving high performances for given storage limitations.